package com.test.daily.leetcode.y2022.m07.day0702.v03;

import java.util.PriorityQueue;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/7/2 下午 02:13
 * @version: 1.0
 */
public class Solution {
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        int N = stations.length;
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> {
            return b - a;
        });
        int fuel = startFuel, pre = 0, ans = 0;
        for (int i = 0; i <= N; i++) {
            int cur = i != N ? stations[i][0] : target;
            fuel -= cur - pre;
            while (fuel < 0 && pq.size() > 0) {
                fuel += pq.poll();
                ans++;
            }
            if (fuel < 0) {
                return -1;
            }
            pq.add(stations[i][1]);
            pre = stations[i][0];
        }
        return ans;
    }
}
